﻿#include <iostream>

//双指针
//常见的双指针有两种形式,⼀种是对撞指针,⼀种是左右指针
//对撞指针:
//	⼀般⽤于顺序结构中,也称左右指针
//	对撞指针从两端向中间移动	⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼近
//	对撞指针的终⽌条件⼀般是两个指针相遇或者错开	(也可能在循环内部找到结果直接跳出循环)
//		也就是:	left == right (两个指针指向同⼀个位置) left > right (两个指针错开)
//快慢指针:
//	⼜称为龟兔赛跑算法
//	其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动
//	这种方法对于处理环形链表或数组非常有用
//	其实不单单是环形链表或者是数组,如果我们要研究的问题出现循环往复的情况时,均可考虑使用快慢指针的思想
//	快慢指针的实现方式有很多种,最常用的⼀种就是:	在⼀次循环中,每次让慢的指针向后移动⼀位,而快的指针往后移动两位,实现⼀快⼀慢

//移动零
//给定⼀个数组nums,编写⼀个函数将所有0移动到数组的末尾,同时保持非零元素的相对顺序
//请注意,必须在不复制数组的情况下原地对数组进行操作
//输⼊ : nums = [0, 1, 0, 3, 12]
//输出: [1, 3, 12, 0, 0]
#include <vector>
void moveZeroes(std::vector<int>& nums)
{
    // 数组划分,分块
    size_t dest = 0;    //dest指向已处理区间中,零元素第一个位置
    size_t cur = 0;     //cur将数组划分为处理过的区间和未处理过的区间
    // [0, dest - 1]    [dest, cur - 1] [cur, nums.size]
    // 已处理非零元素    已处理零元素    未处理元素 
    while (true)
    {
        while (dest < nums.size() && nums[dest])
            ++dest;
        if (dest >= nums.size())
            break;
        cur = dest + 1;
        while (cur < nums.size() && !nums[cur])
            ++cur;
        if (cur >= nums.size())
            break;
        std::swap(nums[dest], nums[cur]);
    }

    //Other plan 原理相同
    //for (int cur = 0, dest = -1; cur < nums.size(); ++cur)
    //    if (nums[cur])
    //        std::swap(nums[dest], nums[cur]);
}

//复写零
//给⼀个⻓度固定的整数数组arr,请你将该数组中出现的每个零都复写⼀遍,并将其余的元素向右平移
//  不要在超过该数组⻓度的位置写入元素,请对输入的数组就地进行上述修改,不要从函数返回任何东西
//输入:   arr = [1, 0, 2, 3, 0, 4, 5, 0]
//输出:   [1, 0, 0, 2, 3, 0, 0, 4]
void duplicateZeros(std::vector<int>& arr)
{
    size_t cnt = 0;
    size_t i = 0;
    // 找到需要复写的零的数量和最后一个数
    for (i = 0; i + cnt < arr.size(); ++i)
    {
        if (arr[i] == 0)
            ++cnt;
    }
    // 处理边界,可能有一个0不能复写
    bool flag = false;
    if (i + cnt > arr.size())
        flag = true, --cnt;
    // 从后开始拷贝元素,复写0
    for (size_t end = arr.size() - 1; cnt != 0; --end)
    {
        arr[end] = arr[end - cnt];
        if (arr[end] == 0)
        {
            if (!flag)
            {
                --cnt;
                arr[--end] = 0;
            }
            else
                flag = false;
        }
    }
}

//快乐数
//编写⼀个算法来判断⼀个数n是不是快乐数
//快乐数定义为:
//  对于⼀个正整数,每⼀次将该数替换为它每个位置上的数字的平⽅和
//  然后重复这个过程直到这个数变为1,也可能是⽆限循环但始终变不到1
//  如果这个过程结果为1,那么这个数就是快乐数
#include <unordered_set>
bool isHappy(int n)
{
    //std::unordered_set<int> map;
    //int prev = n;
    //while (true)
    //{
    //    int next = 0;
    //    for (int tmp = prev; tmp; tmp /= 10)
    //        next += (tmp % 10) * (tmp % 10);
    //    if (next == 1)
    //        return true;
    //    if (map.find(next) != map.end())
    //        break;
    //    map.insert(next);
    //    prev = next;
    //}
    //return false;

    // 快慢指针
    int prev_slow = n;
    int prev_fast = n;
    while (true)
    {
        // 慢指针一次走一步
        int next_slow = 0;
        for (int tmp = prev_slow; tmp; tmp /= 10)
            next_slow += (tmp % 10) * (tmp % 10);

        // 快指针一次走两步
        int next_fast = 0;
        for (int tmp = prev_fast; tmp; tmp /= 10)
            next_fast += (tmp % 10) * (tmp % 10);
        int next_fast_two = 0;
        for (int tmp = next_fast; tmp; tmp /= 10)
            next_fast_two += (tmp % 10) * (tmp % 10);

        // 无论是变不成1,还是可以变为1,都会有一个环,快慢指针一定会相遇
        if (next_fast_two == next_slow)
        {
            // 只需判断环内元素是否为1即可
            if (next_fast_two == 1)
                return true;
            else
                return false;
        }

        prev_slow = next_slow;
        prev_fast = next_fast_two;
    }
    return false;
}

//盛水最多的容器
//给定⼀个长度为n的整数数组height.有n条垂线,第i条线的两个端点是(i, 0)和(i,height[i])
//    找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水,返回容器可以储存的最大水量
//  输入: [1, 8, 6, 2, 5, 4, 8, 3, 7]
//  输出: 49
size_t maxArea(std::vector<int>& height)
{
    // int max = 0;
    // for (size_t i = 0; i < height.size(); ++i)
    // {
    //     for (size_t j = i + 1; j < height.size(); ++j)
    //     {
    //         int result = std::min(height[i], height[j]) * (j - i);
    //         if (result > max)
    //             max = result;
    //     }
    // }

    size_t max = 0;
    // 双指针,从两侧开始,计算面积,每次计算完成后,都移动短板,因此不会错过面积最大值
    // 在每个状态下,无论长板或短板向中间收窄一格,都会导致水槽底边宽度−1变短
    // 若向内移动短板,水槽的短板可能变大,因此下个水槽的面积可能增大
    // 若向内移动长板,水槽的短板​不变或变小,因此下个水槽的面积一定变小
    for (size_t i = 0, j = height.size() - 1; i <= j; )
    {
        size_t result = std::min(height[i], height[j]) * (j - i);
        if (result > max)
            max = result;
        if (height[i] < height[j])
            ++i;
        else
            --j;
    }
    return max;
}

//有效三角形的个数
//给定⼀个包含非负整数的数组nums,返回其中可以组成三角形三条边的三元组个数
//  输入: nums = [2, 2, 3, 4]
//  输出: 3
//      有效的组合是:
//      2, 3, 4(使用第⼀个2)   2, 3, 4(使用第⼆个2)  2, 2, 3
#include <algorithm>
size_t triangleNumber(std::vector<int>& nums)
{
    // 对数组进行排序,升序
    std::sort(nums.begin(), nums.end());
    size_t begin = 0;
    // 保证忽略0
    while (begin < nums.size() && nums[begin] == 0)
        ++begin;
    size_t res = 0;
    // i列举第一条边
    for (size_t i = begin; i < nums.size(); ++i)
    {
        // j列举第二条边
        for (size_t j = i + 1; j < nums.size(); ++j)
        {
            // 第三条边长度最大值
            size_t third_len = nums[i] + nums[j];
            // 满足条件的最大边位置所在的缩小区间
            // left在二分查找中最后一个小于third_len的元素位置,right最后一个大于等于third_len的元素位置
            size_t left = 0, right = 0;
            // 列出第三条边的区间
            size_t left_f = j + 1, right_f = nums.size() - 1;
            while (left_f <= right_f)
            {
                size_t tmp = (left_f + right_f) / 2;
                if (nums[tmp] < third_len)
                    left = tmp, left_f = tmp + 1;   // 找到最后一个小于third_len的位置计入
                else
                    right = tmp, right_f = tmp - 1; // 找到最后一个大于third_len的位置计入
                // 当缩小区间的两侧都找到后跳出
                if (left && right)
                    break;
            }
            // 小区间左测找不到,没有比third_len更小的值,无边满足条件
            if (left == 0)
                continue;
            // 小区间右测找不到,没有比third_len更大的值,全部边满足条件
            if (right == 0)
                right = nums.size();
            // 在小区间中查找最后一个满足第三条边的元素位置
            while (left < right)
            {
                if (nums[left] < third_len)
                    ++left;
                else
                    break;
            }
            size_t index = left - 1;
            // 在该位置中,从j到index中的边全部满足条件
            res += index - j;
        }
    }
    return res;
}

//三数之和
//给⼀个整数数组nums,判断是否存在三元组[nums[i],nums[j],nums[k]]满足i != j,i != k,j != k,同时还满足nums[i]+nums[j]+nums[k]==0
//请返回所有和为0且不重复的三元组
//注意,答案中不可以包含重复的三元组
//输入: nums = [-1, 0, 1, 2, -1, -4]
//输出: [[-1, -1, 2], [-1, 0, 1]]
//      nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0
//      nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0
//      nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0
//不同的三元组是[-1, 0, 1]和[-1, -1, 2]
//注意,输出的顺序和三元组的顺序并不重要
std::vector<std::vector<int>> threeSum(std::vector<int>& nums)
{
    // 先对整个数组进行排序,升序
    std::sort(nums.begin(), nums.end());
    std::vector<std::vector<int>> ret;
    // 选中一个数,在其后的区间中使用双指针遍历
    for (size_t i = 0; i < nums.size(); )
    {
        // 当i大于0时,其后所有的元素全部大于0,三数和不可能等于0
        if (nums[i] > 0)
            break;
        // 在区间中找合适的数
        size_t left = i + 1, right = nums.size() - 1;
        int target = -nums[i];
        while (left < right)
        {
            // 遍历
            int sum = nums[left] + nums[right];
            
            if (sum > target)
                --right;    // 若二数之和大于目标,right所选数偏大
            else if (sum < target)
                ++left;    // 若二数之和小于目标,left所选数偏小
            else
            {
                // 找到就放入
                ret.push_back({ nums[i], nums[left], nums[right] });
                ++left, --right;
                // 对left,right所指向元素去重,防止被重复包含
                while (left < right && nums[left - 1] == nums[left])
                    ++left;
                while (left < right && nums[right + 1] == nums[right])
                    --right;
            }
        }
        ++i;
        // 对所选目标数进行去重
        while (i < nums.size() && nums[i - 1] == nums[i])
            ++i;
    }
    return ret;
}
//四数之和
//给你⼀个由n个整数组成的数组nums,和⼀个⽬标值target,请找出并返回满足下述全部条件且不重复的四元组
//[nums[a],nums[b],nums[c],nums[d]](若两个四元组元素⼀⼀对应,则认为两个四元组重复)
//  a,b,c,,d互不相同,nums[a]+nums[b]+nums[c]+nums[d]==target
//可以按任意顺序返回答案
//输入: nums = [1, 0, -1, 0, -2, 2], target = 0
//输出: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
std::vector<std::vector<int>>fourSum(std::vector<int>& nums, int target)
{
    // 大致思路同三数之和相同
    std::sort(nums.begin(), nums.end());
    std::vector<std::vector<int>> ret;
    for (size_t i = 0; i < nums.size(); )   // 固定数nums[i]
    {
        long long target_i = target - nums[i];  // 找寻三数之和为target - nums[i]
        for (size_t j = i + 1; j < nums.size(); )   // 固定数nums[j]
        {
            long long target_j = target_i - nums[j];    // 找寻两数之和target - nums[i] - nums[j]
            size_t left = j + 1, right = nums.size() - 1;   // 双指针区间找
            while (left < right)
            {
                int sum = nums[left] + nums[right];
                if (sum > target_j)
                    --right;
                else if (sum < target_j)
                    ++left;
                else
                {
                    ret.push_back({ nums[i], nums[j], nums[left], nums[right] });
                    ++left, --right;
                    // 双指针区间指向元素去重
                    while (left < right && nums[left - 1] == nums[left])
                        ++left;
                    while (left < right && nums[right + 1] == nums[right])
                        --right;
                }
            }
            // 固定数j去重
            ++j;
            while (j < nums.size() && nums[j - 1] == nums[j])
                ++j;
        }
        // 固定数i去重
        ++i;
        while (i < nums.size() && nums[i - 1] == nums[i])
            ++i;
    }
    return ret;
}

//滑动窗口

//长度最小的子数组
//给定⼀个含有n个正整数的数组和⼀个正整数target
//找出该数组中满足其和大于等于target的长度最小的连续子数组[numsl, numsl + 1, ..., numsr - 1, numsr],并返回其长度
//如果不存在符合条件的子数组,返回0
//输入: target = 7, nums = [2, 3, 1, 2, 4, 3]
//输出: 2
//  子数组[4, 3]是该条件下的长度最小的子数组
int minSubArrayLen(int target, std::vector<int>& nums)
{
    size_t ret = (size_t)-1;
    int sum = 0;
    // 设置滑动窗口的区间
    for (size_t left = 0, right = 0; right < nums.size(); )
    {
        // sum累加该窗口区间内元素的值
        sum += nums[right];
        // sum满足条件,大于等于target
        while (sum >= target)
        {
            // 计算该窗口大小
            size_t len = right - left;
            if (ret > len)
                ret = len;
            // 将窗口减少一位
            sum -= nums[left];
            // 因为sum中的结果为窗口内元素总和,所以left <= right
            ++left;
        }
        ++right;
    }
    return ret + 1;
}

//无重复字符的最长子串
//给定⼀个字符串s,请找出其中不含有重复字符的最长子串的长度
//输⼊: s = "abcabcbb"
//输出: 3
//  因为无重复字符的最长⼦串是abc,所以其长度为3
#include <string>
int lengthOfLongestSubstring(std::string s)
{
    // 设置映射,map中存放出现该元素在s的下标
    std::vector<int> map(255, -1);
    int len = -1;
    // 双指针,滑动窗口
    for (size_t left = 0, right = 0; right < s.size(); ++right)
    {
        // 若当前元素该字串中在出现过
        if (map[s[right]] != -1)
        {
            size_t pos = map[s[right]];
            // 将left后推至该重复元素的下一个位置,并将在两个位置中间出现的元素在map中的映射下标置为-1
            while (left <= pos)
                map[s[left++]] = -1;
        }
        // 在map中映射当前元素的下标
        map[s[right]] = right;
        // 计算当前串的长度
        if ((int)(right - left) > len)
            len = right - left;
    }
    return len + 1;
}

//最大连续1的个数
//给定⼀个⼆进制数组nums和⼀个整数k,如果可以翻转最多k个0,则返回数组中连续1的最大个数
//输入: nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], K = 2
//输出: 6
//  [1, 1, 1, 0, 0, 0 -> 1, 1, 1, 1, 1, 0 -> 1]
int longestOnes(std::vector<int>& nums, int k)
{
    // 双指针,滑动窗口
    size_t left = 0, right = 0;
    // 记录在该窗口中已翻转的零的个数
    size_t cnt = 0;
    size_t max = 0;
    while (right < nums.size())
    {
        // 若该位置为0,则记录翻转
        if (nums[right] == 0)
            ++cnt;
        // 当翻转的0的个数超出限制
        if (cnt > k)
        {
            // 移动左区间过一个零,让窗口内翻转的0的个数至合理范围内
            ++left;
            while (nums[left - 1] != 0)
                ++left;
            --cnt;
        }
        ++right;
        if (max < right - left)
            max = right - left;
    }
    return max;
}

//将x减到0的最小操作数
//给⼀个整数数组nums和⼀个整数x,每⼀次操作时,你应当移除数组nums最左边或最右边的元素,然后从x中减去该元素的值
//请注意,需要修改数组以供接下来的操作使用
//如果可以将x恰好减到0,返回最小操作数,否则,返回-1
//输入: nums = [1, 1, 4, 2, 3], x = 5
//输出: 2
//  最佳解决方案是移除后两个元素，将x减到0
int minOperations(std::vector<int>& nums, int x)
{
    // left指向前缀和的end    right指向前缀和的begin
    size_t left = 0, right = 0;
    // 前缀和 + 后缀和
    int sum = 0;
    for (size_t i = 0; i < nums.size(); ++i)
        sum += nums[i];
    int min = nums.size() + 1;
    while (true)
    {
        // 当sum > target时
        if (sum > x)
        {
            // 当sum大于target,且后缀和为零时,结束
            if (right >= nums.size())
                break;
            // 后缀 -= 当前元素,后缀-1
            sum -= nums[right];
            ++right;
        }
        else if (sum < x)
        {
            // 当sum小于target,且前缀和的end与后缀和的begin指向相同位置时,结束
            if (left > right)
                break;
            // 前缀 += 当前元素,前缀-1
            sum += nums[left];
            ++left;
        }
        else
        {
            // sum == x时
            int len = left + (nums.size() - right);
            if (len < min)
                min = len;
            // 判断是否还有其他满足条件的前缀和 + 后缀和
            if (left <= right && right < nums.size())
            {
                sum += nums[left];
                sum -= nums[right];
                ++left, ++right;
            }
            else
                break;
        }
    }
    if (min == nums.size() + 1)
        return -1;
    else
        return min;
}

//水果成篮
//农场从左到右种植了⼀排果树,这些树⽤⼀个整数数组fruits表示,其中fruits[i]是第i棵树上的水果种类
//要尽可能多地收集水果,但必须按照要求采摘水果
//  只有两个篮⼦,并且每个篮⼦只能装单⼀类型的水果,每个篮子能够装的水果总量没有限制
//  可以选择任意⼀棵树开始采摘,你必须从每棵树(包括开始采摘的树)上恰好摘⼀个水果
//  采摘的水果应当符合篮⼦中的水果类型,每采摘⼀次,你将会向右移动到下⼀棵树,并继续采摘
//  ⼀旦你走到某棵树前,但水果不符合篮⼦的水果类型,那么就必须停⽌采摘
//给你⼀个整数数组fruits,返回你可以收集的水果的最大数⽬
//输入: fruits = [0, 1, 2, 2]
//输出: 3
//  可以采摘[1, 2, 2]这三棵树,如果从第⼀棵树开始采摘,则只能采摘[0, 1]这两棵树
//输入: fruits = [3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4]
//输出: 5
//  可以采摘[1, 2, 1, 1, 2]这五棵树
int totalFruit(std::vector<int>& fruits)
{
    // 滑动窗口
    size_t left = 0, right = 0;
    int max = 0;
    // 篮子中水果的种类
    int map[2] = { -1, -1 };
    while (right < fruits.size())
    {
        // 当两个篮子的水果种类没选择时
        if (map[0] == -1 || map[1] == -1)
        {
            // 保证一个种类水果不会占两个篮子
            if (map[0] == -1 && map[1] != fruits[right])
                map[0] = fruits[right];
            else if (map[1] == -1 && map[0] != fruits[right])
                map[1] = fruits[right];
        }
        else if (map[0] != fruits[right] && map[1] != fruits[right])
        {
            // 当第三种水果出现时
            // left从当前位置向前找到和当前类型挨着的水果类型
            left = right - 1;
            // 将篮子中另一种水果类型换成当前类型
            if (map[0] == fruits[left])
                map[1] = fruits[right];
            else
                map[0] = fruits[right];
            // 找到left指向水果的连续第一次出现位置
            while (left > 0 && fruits[left - 1] == fruits[left])
                --left;
        }
        ++right;
        if (max < right - left)
            max = right - left;
    }
    return max;
}

//找到字符串中所有字母异位词
//给定两个字符串s和p,找到s中所有p的异位词的子串,返回这些子串的起始索引
//  不考虑答案输出的顺序
//异位词指由相同字母重排列形成的字符串(包括相同的字符串)
//输入: s = "cbaebabacd", p = "abc"
//输出: [0, 6]
//起始索引等于0的子串是"cba",它是"abc"的异位词
//起始索引等于6的子串是"bac",它是"abc"的异位词
#include <map>
std::vector<int> findAnagrams(std::string s, std::string p)
{
    // 记录p中所出现的字符及次数
    std::map<char, int> map_p;
    for (size_t i = 0; i < p.size(); ++i)
        ++map_p[p[i]];
    std::vector<int> ret;
    // 滑动窗口
    size_t left = 0, right = 0;
    // 记录当前窗口内的字符出现次数
    std::map<char, int> map_find;
    while (right < s.size())
    {
        // 若当前字符不在p中存在,map_find清空
        if (map_p.find(s[right]) == map_p.end())
        {
            map_find.clear();
            // 窗口指向下一个位置
            left = ++right;
        }
        else
        {
            // 当前字符存在p中,记录出现次数
            ++map_find[s[right]];
            // 若在窗口内出现次数大于在p中出现次数
            if (map_find[s[right]] > map_p[s[right]])
            {
                // 消除该字符出现的次数直至等于在p中出现次数
                while (map_find[s[right]] > map_p[s[right]])
                {
                    --map_find[s[left]];
                    ++left;
                }
            }
            // right向后移动保证指向位置为窗口end
            ++right;
        }
        // 若窗口长度为p,则找到了
        if (right - left == p.size())
            ret.push_back(left);
    }
    return ret;
}
std::vector<int> findSubstring(std::string s, std::vector<std::string>& words)
{
    std::map<std::string, int> map_words;
    for (const auto& e : words)
        ++map_words[e];

    std::vector<int> ret;
    size_t len = words[0].size();
    size_t left = 0, right = 0;
    std::map<std::string, int> map_s;
    while (left + len * words.size() <= s.size())
    {
        std::string tmp = s.substr(right, len);
        if (map_words.find(tmp) == map_words.end())
        {
            map_s.clear();
            left = ++right;
        }
        else
        {
            ++map_s[tmp];
            if (map_s[tmp] > map_words[tmp])
            {
                map_s.clear();
                right = ++left;
            }
            else
                right += len;
        }
        if (right - left == len * words.size())
        {
            ret.push_back(left);
            map_s.clear();
            right = ++left;
        }
    }
    return ret;
}

//最小覆盖⼦串
//给你⼀个字符串s,⼀个字符串t.返回s中涵盖t所有字符的最小子串如果s中不存在涵盖t所有字符的子串,则返回空字符串""
//对于t中重复字符,我们寻找的子字符串中该字符数量必须不少于t中该字符数量
//如果s中存在这样的子串,我们保证它是唯⼀的答案
//输入: s = "ADOBECODEBANC", t = "ABC"
//输出: "BANC"
//  最小覆盖子串"BANC"包含来⾃字符串t的'A','B','C'
std::string minWindow(std::string s, std::string t)
{
    int t_map[128] = { 0 }; // 统计字符串t中每⼀个字符的频次
    int kinds = 0; // 统计有效字符有多少种
    for (auto ch : t)
    {
        if (t_map[ch]++ == 0)
            kinds++;
    }
    int s_map[128] = { 0 }; // 统计窗口内每个字符的频次
    int minlen = INT_MAX, begin = -1;
    for (int left = 0, right = 0, count = 0; right < s.size(); right++)
    {
        char in = s[right];
        if (++s_map[in] == t_map[in])
            count++; // 进窗口 + 维护 count
        while (count == kinds) // 判断是否满足
        {
            if (right - left + 1 < minlen)  // 更新结果
            {
                minlen = right - left + 1;
                begin = left;
            }
            char out = s[left++];
            if (s_map[out]-- == t_map[out]) // 出窗口 + 维护 count
                count--;
        }
    }
    if (begin == -1)
        return "";
    else
        return s.substr(begin, minlen);
}

//⼆分

//⼆分查找
//给定⼀个n个元素有序的(升序)整型数组nums和⼀个⽬标值target,写⼀个函数搜索nums中的target,如果⽬标值存在返回下标,否则返回-1
//输入: nums = [-1, 0, 3, 5, 9, 12], target = 9
//输出: 4
//  9出现在nums中并且下标为4
int search(std::vector<int>& nums, int target)
{
    // 基础二分查找
    int left = 0, right = nums.size() - 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (nums[mid] == target)
            break;
        else if (nums[mid] > target)
            right = mid - 1;
        else
            left = mid + 1;
    }
    if (left <= right)
        return (left + right) / 2;
    else
        return -1;
}

//在排序数组中查找元素的第⼀个和最后⼀个位置
//给你⼀个按照非递减顺序排列的整数数组nums,和⼀个⽬标值target,请你找出给定⽬标值在数组中的开始位置和结束位置
//如果数组中不存在⽬标值target,返回[-1, -1]
//你必须设计并实现时间复杂度为O(logn)的算法解决此问题
//输入: nums = [5, 7, 7, 8, 8, 10], target = 8
//输出: [3, 4]
std::vector<int> searchRange(std::vector<int>& nums, int target)
{
    // 基础二分查找
    int left = 0, right = nums.size() - 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (nums[mid] > target)
            right = mid - 1;
        else if (nums[mid] < target)
            left = mid + 1;
        else
            break;
    }
    // 若没有找到
    if (left > right)
        return { -1, -1 };
    else
    {
        // 找到的目标值
        int mid = (left + right) / 2;
        // 找到左边界
        for (int i = mid; i >= 0 && nums[i] == nums[mid]; --i)
            left = i;
        // 找到右边界
        for (int i = mid; i < nums.size() && nums[i] == nums[mid]; ++i)
            right = i;
        return { left, right };
    }
}

//搜索插入位置
//给定⼀个排序数组和⼀个⽬标值,在数组中找到⽬标值,并返回其索引,如果⽬标值不存在于数组中,返回它将会被按顺序插入的位置
//请必须使用时间复杂度为O(logn)的算法
//输入: nums = [1, 3, 5, 6], target = 5
//输出: 2
int searchInsert(std::vector<int>& nums, int target)
{
    // 基础二分查找
    int left = 0, right = nums.size() - 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (nums[mid] > target)
            right = mid - 1;
        else if (nums[mid] < target)
            left = mid + 1;
        else
            break;
    }
    // 若该数没有找到,则right+1的位置就是最小的大于target的元素位置
    if (left > right)
        return right + 1;
    else
    {
        // 若该数找到,则查找该数的第一次出现的位置
        int mid = (left + right) / 2;
        for (int i = mid; i >= 0 && nums[i] == nums[mid]; --i)
            left = i;
        return left;
    }
}

//x的平方根
//给你⼀个非负整数x,计算并返回x的算术平方根
//由于返回类型是整数,结果只保留整数部分,小数部分将被舍去
//注意: 不允许使用任何内置指数函数和算符,如pow(x, 0.5)或者x ** 0.5
//输入: x = 8
//输出: 2
//  8的算术平方根是2.82842...,由于返回类型是整数,小数部分将被舍去
int mySqrt(int x)
{
    // 二分查找
    unsigned int left = 0, right = x;
    while (left <= right)
    {
        unsigned long long mid = (left + right) / 2;
        // 每次判断中间值的平方与x的大小
        if (mid * mid > x)
            right = mid - 1;
        else if (mid * mid < x)
            left = mid + 1;
        else
            return mid;
    }
    return right;
}

//山峰数组的峰顶
//符合下列属性的数组arr称为山脉数组
//  arr.length >= 3,存在i(0 < i < arr.length - 1),使得: arr[0] < arr[1] < ... arr[i - 1] < arr[i], arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
//给你由整数组成的山脉数组arr,返回任何满足arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1]的下标i
//输入: arr = [0, 1, 0]
//输出: 1
int peakIndexInMountainArray(std::vector<int>& arr)
{
    // 二分查找
    int left = 0, right = arr.size() - 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if ((mid == 0 || arr[mid] > arr[mid - 1]) \
            && (mid == arr.size() - 1 || arr[mid] < arr[mid + 1]))
            left = mid + 1; // 若当前元素为上升趋势,left移动
        else if ((mid == 0 || arr[mid] < arr[mid - 1]) \
            && (mid == arr.size() - 1 || arr[mid] > arr[mid + 1]))
            right = mid - 1;     // 若当前元素为下降趋势,right移动
        else
            break;
    }
    return ((left + right) / 2);
}

//寻找峰值
//峰值元素是指其值严格大于左右相邻值的元素
//给你一个整数数组nums,找到峰值元素并返回其索引.数组可能包含多个峰值,在这种情况下,返回任何⼀个峰值所在位置即可
//你可以假设nums[-1] = nums[n] = 负无穷,你必须实现时间复杂度为O(logn)的算法来解决此问题
//输入: nums = [1, 2, 3, 1]
//输出: 2
//  3是峰值元素,你的函数应该返回其索引2
int findPeakElement(std::vector<int>& nums)
{
    // 二分查找
    int left = 0, right = nums.size() - 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        // 若当前元素满足峰值条件,break
        if ((mid == 0 || nums[mid] > nums[mid - 1]) \
            && (mid == nums.size() - 1 || nums[mid] > nums[mid + 1]))
            break;
        else if (mid == 0 || nums[mid] > nums[mid - 1])
            left = mid + 1; // 若当前元素呈上升趋势,left移动
        else
            right = mid - 1;    // 否则right移动
    }
    return (left + right) / 2;
}

//搜索旋转排序数组中的最小值
//整数数组nums按升序排列,数组中的值互不相同
//在传递给函数之前,nums在预先未知的某个下标k(0 <= k < nums.length)上进行了旋转
//使数组变为[nums[k], nums[k + 1], ..., nums[n - 1], nums[0], nums[1], ..., nums[k - 1]](下标从0开始计数)
//给你旋转后的数组nums查找其最小值返回它的下标
//你必须设计⼀个时间复杂度为O(logn)的算法解决此问题
//输入: nums = [3,4,5,1,2]
//输出: 1
//  原数组为[1, 2, 3, 4, 5],旋转3次得到输入数组
int findMin(std::vector<int>& nums)
{
    // 二分查找
    // 将整体数组分为两部分,左侧升序,右侧升序
    int left = 0, right = nums.size() - 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        // 若当前元素与left和right元素呈升序,则left即为目标
        if (nums[mid] <= nums[right] && nums[mid] >= nums[left])
            return nums[left];
        else if (nums[mid] >= nums[left] && nums[mid] >= nums[right])
            left = mid + 1; // 若当前位置在左部分升序,left移动
        else if (nums[mid] <= nums[left] && nums[mid] <= nums[right])
            right = mid; // 若当前位置在右部分升序,right移动
    }
    return 0;
}

//0 - n-1中缺失的数字
//⼀个⻓度为n-1的递增排序数组中的所有数字都是唯⼀的,并且每个数字都在范围0 - n-1之内
//在范围0 - n-1内的n个数字中有且只有⼀个数字不在该数组中,请找出这个数字
//输⼊: [0, 1, 3]
//输出: 2
int takeAttendance(std::vector<int>& records)
{
    // 二分查找
    int left = 0, right = records.size() - 1;
    while (left < right)
    {
        int mid = (left + right) / 2;
        // 若当前数字没错序,表示[left, mid]之间不缺
        if (records[mid] == mid)
            left = mid + 1;
        else if (records[mid] > mid)
            right = mid;    // 当前数字错序,表示[left, mid]之间缺少
    }
    // 额外判断n元素是否出现
    return records[left] == left ? left + 1 : left;
}

//前缀和

//⼀维前缀和
//给定一个长度为n的数组a1,a2, ... an,接下来有q次查询,每次查询有两个参数l,r.
//对于每个询问,请输出al + al+1 + ... + ar
//输入描述:
//第一行包含两个整数n和q,第二行包含n个整数,表示a1,a2, ... an
//接下来q行,每行包含两个整数l和r
//输出q行,表示每次查询的结果
//输入:
//3 2
//1 2 4
//1 2
//2 3
//输出:
//3
//6
int algorithm_1()
{
    int n = 0, q = 0;
    std::cin >> n >> q;
    // 多扩容一位,忽略越界问题
    std::vector<long> v(n + 1, 0);
    for (int i = 1; i <= n; ++i)
    {
        // 存入数据
        std::cin >> v[i];
        // 累加计算前缀和
        v[i] += v[i - 1];
    }

    for (int i = 0; i < q; ++i)
    {
        int l = 0, r = 0;
        std::cin >> l >> r;
        // [1, r] - [1, left - 1] = [left, r]
        std::cout << (v[r] - v[l - 1]) << std::endl;
    }
    return 0;
}

//⼆维前缀和
//给你一个n行m列的矩阵A,下标从1开始
//接下来有q次查询,每次查询输入4个参数x1,y1,x2,y2
//请输出以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和
//输入描述:
//第一行包含三个整数n, m, q
//接下来n行,每行m个整数,代表矩阵的元素
//接下来q行,每行4个整数x1,y1,x2,y2分别代表这次查询的参数
//输入:
//3 4 3
//1 2 3 4
//3 2 1 0
//1 5 7 8
//1 1 2 2
//1 1 3 3
//1 2 3 4
//输出:
//8
//25
//32
int algorithm_2()
{
    int n = 0, m = 0, q = 0;
    std::cin >> n >> m >> q;
    // 多扩容一位,忽略越界问题
    std::vector<std::vector<long long>> v(n + 1, std::vector<long long>(m + 1, 0));
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            std::cin >> v[i][j];
            // [1, 1 --> i - 1, j]和[1, 1 --> i, j - 1]中都含有[1, 1 --> i - 1, j  -1],应减去一个
            // 累加 [1, 1 --> i, j] = [1, 1 --> i - 1, j] + [1, 1 --> i, j - 1] - [1, 1 --> i - 1, j - 1]
            v[i][j] += v[i - 1][j] + v[i][j - 1] - v[i - 1][j - 1];
        }
    }
    for (int i = 0; i < q; ++i)
    {
        int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
        std::cin >> x1 >> y1 >> x2 >> y2;
        // [1, 1 --> x2 - 1, y1]和[1, 1 --> x1, y2 - 1]中都含有[1, 1 --> x1 - 1, y1  -1],应加上一个
        // [x1, y1 --> x2, y2] = [1, 1 --> x1, y2] - [1, 1 --> x1, y2 - 1] - [1, 1 --> x2 - 1, y1] + [1, 1 --> x1 - 1, y1 - 1]
        long long res = v[x2][y2] - v[x1 - 1][y2] - v[x2][y1 - 1] + v[x1 - 1][y1 - 1];
        std::cout << res << std::endl;
    }
    return 0;
}

//寻找数组的中心下标
//给你⼀个整数数组nums,请计算数组的中心下标
//数组中心下标是数组的⼀个下标,其左侧所有元素相加的和等于右侧所有元素相加的和
//如果中心下标位于数组最左端,那么左侧数之和视为0,因为在下标的左侧不存在元素,这⼀点对于中心下标位于数组最右端同样适用
//如果数组有多个中心下标,应该返回最靠近左边的那⼀个,如果数组不存在中心下标,返回-1
//输入: nums = [1, 7, 3, 6, 5, 6]
//输出: 3
//  左侧数之和sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
//  右侧数之和sum = nums[4] + nums[5] = 5 + 6 = 11,⼆者相等
int pivotIndex(std::vector<int>& nums)
{
    // 双指针 + 前缀和
    long long left = 0, right = 0;
    // 记录第一个数右侧和
    for (size_t i = 1; i < nums.size(); ++i)
        right += nums[i];
    for (size_t i = 0; i < nums.size(); ++i)
    {
        if (left == right)
            return i;
        // 移动一位,左侧和+,右侧和-
        left += nums[i];
        if (i + 1 != nums.size())
            right -= nums[i + 1];
    }
    return -1;
}

//除自身以外数组的乘积
//给你⼀个整数数组nums,返回数组answer,其中answer[i]等于nums中除nums[i]之外其余各元素的乘积
//题⽬数据保证数组nums之中任意元素的全部前缀元素和后缀的乘积都在32位整数范围内
//请不要使用除法,且在O(n)时间复杂度内完成此题
//输入: nums = [1, 2, 3, 4]
//输出: [24, 12, 8, 6]
std::vector<int> productExceptSelf(std::vector<int>& nums)
{
    // 前缀积
    std::vector<int> prev(nums.size(), 0);
    prev[0] = 1;
    for (size_t i = 1; i < nums.size(); ++i)
        prev[i] = nums[i - 1] * prev[i - 1];

    // 后缀积
    std::vector<int> next(nums.size(), 0);
    next[nums.size() - 1] = 1;
    for (int i = nums.size() - 2; i >= 0; --i)
        next[i] = nums[i + 1] * next[i + 1];

    std::vector<int> ret(nums.size(), 0);
    for (size_t i = 0; i < nums.size(); ++i)
        ret[i] = prev[i] * next[i];

    return ret;
}

//和为k的子数组
//给你⼀个整数数组nums和⼀个整数k,请你统计并返回该数组中和为k的连续子数组的个数
//输入: nums = [1, 1, 1], k = 2
//输出: 2
#include <unordered_map>
int subarraySum(std::vector<int>& nums, int k)
{
    //将整个数组分为[0, 组成sum - k前缀的元素位置] [组成sum - k前缀的元素位置 + 1 , i] [i + 1, nums.size() - 1]三部分
    std::unordered_map<int, int> hash;
    hash[0] = 1;

    int ret = 0;
    // 累计前缀和
    long long sum = 0;
    for (size_t i = 0; i < nums.size(); ++i)
    {
        sum += nums[i];
        // 若sum - k出现过,即证明[组成sum - k前缀的元素位置 + 1 , i]的和等于k
        if (hash.find(sum - k) != hash.end())
            ret += hash[sum - k];
        ++hash[sum];
    }
    return ret;
}

//和可被K整除的子数组
//给定⼀个整数数组nums和⼀个整数k,返回其中元素之和可被k整除的(连续,非空)子数组的数⽬,子数组是数组的连续部分
//输入: nums = [4, 5, 0, -2, -3, 1], k = 5
//输出: 7
//  有7个子数组满足其元素之和可被k = 5整除,[4, 5, 0, -2, -3, 1],[5],[5, 0],[5, 0, -2, -3],[0],[0, -2, -3],[-2, -3]
int subarraysDivByK(std::vector<int>& nums, int k)
{
    //设i为数组中的任意位置,用sum[i]表示[0, i]区间内所有元素的和
    //想知道有多少个以i为结尾的可被k整除的子数组,就要找到有多少个起始位置为x1,x2,x3 ...使得[x, i]区间内的所有元素的和可被k整除
    //设[0, x-1]区间内所有元素之和等于a,[0, i]区间内所有元素的和等于b,可得(b - a) % k == 0
    //由同余定理可得,[0, x-1]区间与[0, i]区间内的前缀和同余,故[x, i]区间和就可以整除k
    //于是问题就变成,找到在[0, i-1]区间内,有多少前缀和的余数等于sum[i] % k
    std::unordered_map<int, int> hash;
    hash[0] = 1;

    int ret = 0;
    long long sum = 0;
    for (size_t i = 0; i < nums.size(); ++i)
    {
        sum += nums[i];
        int right = (sum % k + k) % k; // 对负数结果取余做处理
        if (hash.find(right) != hash.end())
            ret += hash[right];
        ++hash[right];
    }
    return ret;
}

//连续数组
//给定⼀个⼆进制数组nums,找到含有相同数量的0和1的最长连续子数组,并返回该子数组的长度
//输入: nums = [0, 1]
//输出: 2
//  [0, 1]是具有相同数量0和1的最长连续子数组
int findMaxLength(std::vector<int>& nums)
{
    std::unordered_map<int, int> hash;
    hash[0] = -1;

    // 将0记作-1,可同化为上两道题,和为k的子数组
    int ret = 0, sum = 0;
    for (size_t i = 0; i < nums.size(); ++i)
    {
        if (nums[i] == 0)
            --sum;
        else
            ++sum;
        // 查找[0, i]区间内是否存在[0, x]区间的结果和[0, i]区间的结果相同
        // 若相同,则证明[x+1, i]区间结果为0,即0,1个数相同,长度即为i - x
        if (hash.find(sum) != hash.end())
            ret = (ret > (i - hash[sum])) ? ret : (i - hash[sum]);
        else
            hash[sum] = i;  // 记录x的位置
    }
    return ret;
}

//矩阵区域和
//给你⼀个m * n的矩阵mat和⼀个整数k,请你返回⼀个矩阵answer
//其中每个answer[i][j]是所有满足下述条件的元素mat[r][c]的和
//  i - k <= r <= i + k,j - k <= c <= j + k 且 (r, c) 在矩阵内
//输入: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], k = 1
//输出: [[12, 21, 16], [27, 45, 33], [24, 39, 28]]
std::vector<std::vector<int>> matrixBlockSum(std::vector<std::vector<int>>& mat, int k)
{
    // 前缀和,算法类似二维数组前缀和
    std::vector<std::vector<int>> dp(mat.size() + 1, std::vector<int>(mat[0].size() + 1));
    // 计算前缀和[0, 0 --> i, j]
    for (size_t i = 1; i < dp.size(); i++)
    {
        for (size_t j = 1; j < dp[i].size(); j++)
            dp[i][j] = mat[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
    }

    std::vector<std::vector<int>> ret(mat.size(), std::vector<int>(mat[0].size(), 0));
    for (int i = 0; i < ret.size(); i++)
    {
        for (int j = 0; j < ret[i].size(); j++)
        {
            size_t x1 = std::max<int>(0, i - k) + 1;
            size_t y1 = std::max<int>(0, j - k) + 1;
            size_t x2 = std::min<int>(ret.size() - 1, i + k) + 1;
            size_t y2 = std::min<int>(ret[i].size() - 1, j + k) + 1;
            //ret[i][j] = [0, 0 --> i, j] - [0, 0 --> i - k, j] - [0, 0 --> i, j - k] + [0, 0 --> i - k, j - k]
            ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
        }
    }
    return ret;
}

// 位运算

//判断字符是否唯⼀
//实现⼀个算法,确定⼀个字符串s的所有字符是否全都不同
//输入: s = "leetcode"
//输出: false
bool isUnique(std::string astr)
{
    // 输入只有小写字母,直接使用int类型32位比特位作为map
    int map = 0;
    for (auto e : astr)
    {
        if (map & (0x01 << (e - 'a')))
            return false;
        else
            map |= 0x01 << (e - 'a');
    }
    return true;
}

//丢失的数字
//给定⼀个包含[0, n]中n个数的数组nums,找出[0, n]这个范围内没有出现在数组中的那个数
//输入: nums = [3, 0, 1]
//输出: 2
//  n=3,有3个数字,所以所有的数字都在范围[0, 3]内,2是丢失的数字,因为它没有出现在nums中
int missingNumber(std::vector<int>& nums)
{
    // 利用异或特性,将[0, n]之间所有数字异或进map中
    int map = 0;
    for (int i = 1; i <= nums.size(); ++i)
        map ^= i;

    // 在将nums中的数字挨个与map异或消除,最后map中剩下的数字就是未出现的数字
    for (auto e : nums)
        map ^= e;
    return map;
}

//两整数之和
//给你两个整数a和b,不使用运算符+和-,计算并返回两整数之和
//输入: a = 1, b = 2
//输出: 3
int getSum(int a, int b)
{
    while (b)
    {
        // 二进制序列中两位都为1则产生进位
        int tmp = a & b;
        // a中存放a,b不进位的二进制位
        a = a ^ b;
        // b中存储要进位的二进制位
        b = tmp << 1;
        // 循环至b中无1,即无进位
    }
    return a;
}

//只出现⼀次的数字II
//给你⼀个整数数组nums,除某个元素仅出现⼀次外,其余每个元素都恰出现三次
//请你找出并返回那个只出现了⼀次的元素
//你必须设计并实现线性时间复杂度的算法且不使⽤额外空间来解决此问题
//输入: nums = [2, 2, 3, 2]
//输出: 3
int singleNumber_II(std::vector<int>& nums)
{
    int ret = 0;
    for (size_t i = 0; i < 32; ++i)
    {
        // 记录有几个数字在该比特位有值
        int sum = 0;
        // 遍历nums数组,查看在该比特位的值
        for (auto& e : nums)
        {
            if ((e >> i) & 0x01)
                ++sum;
        }
        // 若出现一次的数字在该比特位有值,sum % 3必定为1
        sum %= 3;
        if (sum == 1)
            ret |= (0x01 << i);
    }
    return ret;
}

//只出现⼀次的数字III
//给你一个整数数组nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次,找出只出现一次的那两个元素,你可以按任意顺序返回答案
//你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
//输入: nums = [1, 2, 1, 3, 2, 5]
//输出: [3, 5]  [5, 3]也是有效的答案
std::vector<int> singleNumber_III(std::vector<int>& nums)
{
    // map异或上所有元素,其结果一定是出现一次的两个元素异或
    int map = 0;
    for (auto& e : nums)
        map ^= e;
    // 找到这两个元素异或不同的比特位
    size_t flag = 0;
    while (flag < 32)
    {
        if ((map >> flag) & 1)
            break;
        ++flag;
    }
    std::vector<int> ret(2, 0);
    for (auto e : nums)
    {
        // 其中比特位为1的放入ret[0],为0的放入ret[1]
        if ((e >> flag) & 1)
            ret[0] ^= e;
        else
            ret[1] ^= e;
    }
    return ret;
}

//消失的两个数字
//给定⼀个数组,包含从1到N所有的整数,但其中缺了两个数字
//在O(N)时间内只用O(1)的空间找到它们,以任意顺序返回这两个数字均可
//输入: [1]
//输出: [2, 3]
std::vector<int> missingTwo(std::vector<int>& nums)
{
    int map = 0;
    // 将1 --> n之间的数全部异或进map中,因nums中少出现两个数,上限为nums.size() + 2
    for (size_t i = 1; i <= nums.size() + 2; ++i)
        map ^= i;
    // 在异或nums中出现的数,就相当于将1 --> n中的数字除nums中丢失的数字外全部异或两次
    for (auto& e : nums)
        map ^= e;
    // map中的值相当与1 --> n中,nums缺失的两个数字异或结果
    size_t flag = 0;
    while (flag < 32)
    {
        // 找到二者异或结果的不同比特位
        if ((map >> flag) & 0x01)
            break;
        ++flag;
    }
    // 根据二者的不同比特位进行分别异或
    std::vector<int> ret(2, 0);
    // 重新将1 --> n中的数字除nums中丢失的数字外全部异或两次
    for (size_t i = 1; i <= nums.size() + 2; ++i)
    {
        if ((i >> flag) & 0x01)
            ret[0] ^= i;
        else
            ret[1] ^= i;
    }
    for (auto& e : nums)
    {
        if ((e >> flag) & 0x01)
            ret[0] ^= e;
        else
            ret[1] ^= e;
    }
    return ret;
}

// 模拟

//替换所有的问号
//给你⼀个仅包含小写英文字母和'?'字符的字符串s,请你将所有的'?'转换为若干小写字母,使最终的字符串不包含任何连续重复的字符
//注意,你不能修改非'?'字符,题⽬测试用例保证除'?'字符之外,不存在连续重复的字符
//在完成所有转换(可能无需转换)后返回最终的字符串,如果有多个解决方案,请返回其中任何⼀个
//可以证明,在给定的约束条件下,答案总是存在的
//输入: s = "?zs"
//输出: "azs"
//  该示例共有25种解决方案,从"azs"到"yzs"都是符合题⽬要求的,只有"z"是⽆效的修改,因为字符串"zzs"中有连续重复的两个'z'
std::string modifyString(std::string s)
{
    // 遍历替换字符串
    for (size_t i = 0; i < s.size(); ++i)
    {
        if (s[i] == '?')
        {
            // 假设要替换成a
            char rep = 'a';
            // 判断当前位置的前一个字符,让rep为前一个字符的下一个
            if (i != 0)
                rep = (s[i - 1] - 'a' + 1) % 26 + 'a';
            // 判断当前位置的后一个字符,让rep为后一个字符的下一个
            if (i + 1 != s.size() && s[i + 1] != '?')
                rep = (s[i + 1] - 'a' + 1) % 26 + 'a';
            // 若后一个字符的下一个等于上一个字符,则前一个字符的下一个必不可能为后一个字符的下一个
            // 让rep为前一个字符的下一个
            if (i != 0 && s[i - 1] == rep)
                rep = (s[i - 1] - 'a' + 1) % 26 + 'a';
            s[i] = rep;
        }
    }
    return s;
}

//提莫攻击
//提莫在t时刻发起攻击意味着艾希在时间区间[t, t + duration - 1](含t和t+duration-1)处于中毒状态
//如果提莫在中毒影响结束前再次攻击,中毒状态计时器将会重置,在新的攻击之后,中毒影响将会在duration秒后结束
//给你⼀个非递减的整数数组timeSeries,其中timeSeries[i]表⽰提莫在timeSeries[i]秒时对艾希发起攻击,以及⼀个表示中毒持续时间的整数duration
//返回艾希处于中毒状态的总秒数
//输入: timeSeries = [1, 4], duration = 2
//输出: 4
//  提莫攻击对艾希的影响如下:
//  第1秒,提莫攻击艾希并使其立即中毒中毒状态会维持2秒,即第1秒和第2秒
//  第4秒,提莫再次攻击艾希,艾希中毒状态⼜持续2秒,即第4秒和第5秒
//  艾希在第1,2,4,5秒处于中毒状态,所以总中毒秒数是4
int findPoisonedDuration(std::vector<int>& timeSeries, int duration)
{
    int ret_time = 0;
    for (size_t i = 0; i < timeSeries.size(); ++i)
    {
        if (i + 1 != timeSeries.size())
        {
            int tmp = timeSeries[i + 1] - timeSeries[i];
            if (tmp > duration)
                ret_time += duration;
            else
                ret_time += tmp;
        }
        else
            ret_time += duration;
    }
    return ret_time;
}

//N字形变换
//将⼀个给定字符串s根据给定的行数numRows,以从上往下,从左到右进行Z字形排列
//⽐如输入字符串为"PAYPALISHIRING"行数为3时,排列如下:
//P   A   H   N
//A P L S I I G
//Y   I   R
//之后,你的输出需要从左往右逐行读取,产生出⼀个新的字符串,比如:"PAHNAPLSIIGYIR"
//输入: s = "PAYPALISHIRING", numRows = 3
//输出: "PAHNAPLSIIGYIR"
std::string convert(std::string s, int numRows) {
    if (numRows == 1)
        return s;

    std::string ret;
    int d = 2 * numRows - 2, n = s.size();

    for (int i = 0; i < n; i += d)
        ret += s[i];
    for (int k = 1; k < numRows - 1; k++)
    {
        for (int i = k, j = d - k; i < n || j < n; i += d, j += d)
        {
            if (i < n)
                ret += s[i];
            if (j < n)
                ret += s[j];
        }
    }
    for (int i = numRows - 1; i < n; i += d)
        ret += s[i];
    return ret;
}

//外观数列
//给定⼀个正整数n,输出外观数列的第n项
//[外观数列]是⼀个整数序列,从数字1开始,序列中的每⼀项都是对前⼀项的描述
//你可以将其视作是由递归公式定义的数字字符串序列:
//countAndSay(1) = "1"
//countAndSay(n)是对countAndSay(n - 1)的描述,然后转换成另⼀个数字字符串
//前五项如下:
//1.     1
//2.     11
//3.     21
//4.     1211
//5.     111221
//第⼀项是数字1
//描述前⼀项,这个数是1即"⼀个1",记作"11"
//描述前⼀项,这个数是11即"⼆个1",记作"21"
//描述前⼀项,这个数是21即"⼀个2+⼀个1",记作"1211"
//描述前⼀项,这个数是1211即"⼀个1+⼀个2+⼆个1",记作"111221"
//输入: n = 4
//输出: "1211"
std::string _countAndSay(std::string num)
{
    std::string ret;
    char prev = num[0];
    int cnt = 0;
    for (size_t i = 0; i < num.size(); ++i)
    {
        if (num[i] == prev)
            ++cnt;
        else
        {
            ret += std::to_string(cnt) + prev;
            prev = num[i];
            cnt = 1;
        }
    }
    ret += std::to_string(cnt) + prev;
    return ret;
}
std::string countAndSay(int n)
{
    std::string num = "1";
    for (size_t i = 1; i < n; ++i)
        num = _countAndSay(num);
    return num;
}

// 根据给定目录结构,构造形成该目录的最少mkdir语句
struct node
{
    std::string name;
    std::vector<std::string> map;
    std::vector<struct node*> next;
};
void find_dir(struct node* dir, std::vector<std::string>& path, std::string str = "mkdir -p ")
{
    for (size_t i = 0; i < dir->map.size(); ++i)
    {
        str += "/" + dir->map[i];
        if (dir->next[i]->next.size() != 0)
            find_dir(dir->next[i], path, str);
        else
            path.push_back(str);
        str.erase(str.size() - dir->map[i].size() - 1);
    }
}
int algorithm_3()
{
    int n = 0;
    while (std::cin >> n)
    {
        std::vector<std::string> v_str;
        struct node dir;
        for (size_t i = 0; i < n; ++i)
        {
            std::string str;
            std::cin >> str;

            size_t left = 0, right = 0;

            struct node* level = &dir;
            while (left != str.size())
            {
                right = ++left;
                while (right != str.size() && str[right] != '/')
                    ++right;
                std::string name = str.substr(left, right - left);
                if (name.size() == 0)
                    break;
                bool flag = true;
                for (size_t i = 0; i < level->map.size(); ++i)
                {
                    if (level->map[i] == name)
                    {
                        level = level->next[i];
                        flag = false;
                        break;
                    }
                }
                if (flag)
                {
                    struct node* cur = new struct node;
                    cur->name = name;
                    level->map.push_back(name);
                    level->next.push_back(cur);
                    level = cur;
                }
                left = right;
            }
        }
        find_dir(&dir, v_str);
        for (const auto& str : v_str)
            std::cout << str << std::endl;
        std::cout << std::endl;
    }
    return 0;
}

//数青蛙
//给你⼀个字符串croakOfFrogs,它表⽰不同青蛙发出的蛙鸣声(字符串"croak")的组合
//由于同⼀时间可以有多只青蛙呱呱作响,所以croakOfFrogs中会混合多个"croak"
//请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数⽬
//要想发出蛙鸣"croak",⻘蛙必须依序输出'c','r','o','a','k'这5个字母
//如果没有输出全部五个字母,那么它就不会发出声音,如果字符串croakOfFrogs不是由若干有效的"croak"字符混合而成,请返回-1 
//输入:croakOfFrogs = "croakcroak"
//输出:1
//  ⼀只⻘蛙"呱呱"两次
//输入:croakOfFrogs = "crcoakroak"
//输出:2
//  最少需要两只青蛙
int minNumberOfFrogs(std::string croakOfFrogs)
{
    // 打表,记录croak中字符的出现
    std::string target = "croak";
    std::vector<int> map(target.size(), 0);

    // 记录croak字符串中每个字符对应下标
    std::unordered_map<char, int> index;
    for (size_t i = 0; i < target.size(); ++i)
        index[target[i]] = i;

    for (auto c : croakOfFrogs)
    {
        // 若为第一个字符c
        if (c == 'c')
        {
            // 首先判断是否可以消除一个k
            if (map[target.size() - 1] != 0)
                --map[target.size() - 1];
            // c出现次数+1
            ++map[0];
        }
        else
        {
            // 出现字符的对应下标
            int i = index[c];
            // 判断该字符的前一个字符是否出现
            if (map[i - 1] == 0)
                return -1;
            // 前一个--,当前++
            --map[i - 1], ++map[i];
        }
    }

    // 查找是否有多余出现的字符
    for (size_t i = 0; i < map.size() - 1; ++i)
    {
        if (map[i] != 0)
            return -1;
    }
    // 返回最后一个k出现的次数,即为最少需要数目
    return map[map.size() - 1];
}

//分治

//快速排序
//颜色分类
//给定⼀个包含红色,白色和蓝色,共n个元素的数组nums,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色,白色,蓝色顺序排列
//我们使⽤整数0,1和2分别表示红色,白色和蓝色
//必须在不使用库的sort函数的情况下解决这个问题
//输入: nums = [2, 0, 2, 1, 1, 0]
//输出: [0, 0, 1, 1, 2, 2]
void sortColors(std::vector<int>& nums)
{
    // 使用三路划分法,将数组分为3部分
    // left指向已排好序的最后一个0,right指向已排好序的第一个2,mid指向已排好序的最后一个1的下一个位置
    // mid遍历,[0, left]为0,(left, mid)为1,[mid, right)为未排序,[right, size]为2
    int left = -1, mid = 0, right = nums.size();
    while (mid < right)
    {
        if (nums[mid] == 2)
            std::swap(nums[mid], nums[--right]);
        else if (nums[mid] == 0)
            std::swap(nums[mid++], nums[++left]);
        else if (nums[mid] == 1)
            ++mid;
    }
}

//快速排序,三路划分
inline size_t get_mid_num(std::vector<int>& nums, size_t left, size_t right)
{
    size_t mid = (left + right) / 2;
    if ((nums[left] <= nums[mid] && nums[mid] <= nums[right]) || (nums[right] <= nums[mid] && nums[mid] <= nums[left]))
        return mid;
    else if ((nums[left] > nums[mid] && nums[left] < nums[right]) || (nums[left] > nums[right] && nums[left] < nums[mid]))
        return mid;
    else
        return right;
}
void qsort(std::vector<int>& nums, size_t left, size_t right)
{
    if (right - left <= 1)
        return;
    size_t cur = get_mid_num(nums, left, right - 1);
    std::swap(nums[cur], nums[left]);
    size_t prev = left, next = right;
    cur = prev + 1;
    while (cur < next)
    {
        if (nums[cur] > nums[prev])
            std::swap(nums[cur], nums[--next]);
        else if (nums[cur] < nums[prev])
            std::swap(nums[cur++], nums[prev++]);
        else if (nums[cur] == nums[prev])
            ++cur;
    }
    qsort(nums, left, prev);
    qsort(nums, next, right);
}

//快速选择算法
//给定整数数组nums和整数k,请返回数组中第k个最大的元素
//请注意,你需要找的是数组排序后的第k个最大的元素而不是第k个不同的元素
//你必须设计并实现时间复杂度为O(n)的算法解决此问题
//输入: [3, 2, 1, 5, 6, 4], k = 2
//输出: 5
#include <queue>
int findKthLargest(std::vector<int>& nums, int k)
{
    // 选第K大,构建K个元素的小堆,返回堆顶元素
    std::priority_queue<int, std::vector<int>, std::greater<int>> queue;
    for (auto e : nums)
    {
        if (queue.size() < k)
            queue.push(e);
        else
        {
            // 当前元素大于堆顶则替换
            if (e > queue.top())
            {
                queue.pop();
                queue.push(e);
            }
        }
    }
    return queue.top();
}

//最小的k个数
//输入整数数组arr,找出其中最小的k个数
//输入: arr = [3, 2, 1], k = 2
//输出: [1, 2] 或者[2, 1]
std::vector<int> inventoryManagement(std::vector<int>& stock, int cnt)
{
    // 构建小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> q;
    for (auto e : stock)
        q.push(e);
    std::vector<int> ret(cnt, 0);
    for (size_t i = 0; i < ret.size(); ++i)
        ret[i] = q.top(), q.pop();
    return ret;
}

// 分治

// 归并排序,递归
void insert_sort(std::vector<int>& nums, int begin, int end)
{
    for (int pos = begin + 1; pos < end; ++pos)
    {
        int tmp = nums[pos];
        int cur = 0;
        for (cur = pos - 1; cur >= begin; --cur)
        {
            if (nums[cur] > tmp)
                nums[cur + 1] = nums[cur];
            else
                break;
        }
        nums[cur + 1] = tmp;
    }
}
void merge_sort_r(std::vector<int>& nums, int begin, int end, std::vector<int>& tmps)
{
    if (end - begin <= 1)
        return;
    if (end - begin <= 10)
        insert_sort(nums, begin, end);

    int mid = (begin + end) / 2;
    merge_sort_r(nums, begin, mid, tmps);
    merge_sort_r(nums, mid, end, tmps);

    int left = begin, right = mid;
    int pos = begin;
    while (left < mid && right < end)
    {
        while (left < mid && nums[left] <= nums[right])
            tmps[pos++] = nums[left++];
        while (right < end && nums[right] <= nums[left])
            tmps[pos++] = nums[right++];
    }
    while (left < mid)
        tmps[pos++] = nums[left++];
    while (right < end)
        tmps[pos++] = nums[right++];

    for (size_t i = begin; i < end; ++i)
        nums[i] = tmps[i];
}
// 非递归
void merge_sort(std::vector<int>& nums, int begin, int end)
{
    std::vector<int> tmps(nums.size(), 0);
    for (int gap = 1; gap < end - begin; gap *= 2)
    {
        int pos = 0;
        for (int i = 0; i + gap < end; i += gap * 2)
        {
            int left_begin = i, left_end = left_begin + gap;
            int right_begin = left_end, right_end = right_begin + gap;
            if (right_end > end)
                right_end = end;
            while (left_begin < left_end && right_begin < right_end)
            {
                if (nums[left_begin] <= nums[right_begin])
                    tmps[pos++] = nums[left_begin++];
                else
                    tmps[pos++] = nums[right_begin++];
            }
            while (left_begin < left_end)
                tmps[pos++] = nums[left_begin++];
            while (right_begin < right_end)
                tmps[pos++] = nums[right_begin++];
        }
        while (pos--)
            nums[pos] = tmps[pos];
    }
}
std::vector<int> sortArray(std::vector<int>& nums)
{
    std::vector<int> ret(nums);
    //qsort(ret, 0, ret.size());
    // std::vector<int> tmp(nums.size(), 0); 
    // merge_sort_r(ret, 0, ret.size(), tmp);
    merge_sort(ret, 0, ret.size());
    return ret;
}

//数组中的逆序对
//在数组中的两个数字,如果前面⼀个数字大于后面的数字,则这两个数字组成⼀个逆序对,输⼊⼀个数组,求出这个数组中的逆序对的总数
//输入: [7, 5, 6, 4]
//输出: 5
void merge_count(std::vector<int>& nums, int begin, int end, int& ret, std::vector<int>& tmp)
{
    if (end - begin <= 1)
        return;
    // 进行归并,将一整个数组分为两部分,左右各自统计好内部的逆序对数量,并排升序
    int mid = (begin + end) / 2;
    merge_count(nums, begin, mid, ret, tmp);
    merge_count(nums, mid, end, ret, tmp);

    // 划分出左右两个数组的范围
    int left_begin = begin, left_end = mid;
    int right_begin = mid, right_end = end;
    // 循环迭代指针,遍历右侧数组,在左侧数组中找寻可以和当前元素构成逆序对的
    int left = left_begin, right = right_begin;
    int pos = left_begin;
    while (left < left_end && right < right_end)
    {
        // 若左侧当前元素小于右侧当前元素,左侧为升序,left++,并将其放入tmp数组中
        if (nums[left] < nums[right])
            tmp[pos++] = nums[left++];
        else if (nums[left] > nums[right])
        {
            // 若左侧当前元素大于右侧当前元素,构成逆序对,且左侧为升序,左侧数组中该元素后所有元素均与其构成逆序对
            // right++,并将其放入tmp数组中
            ret += left_end - left;
            tmp[pos++] = nums[right++];
        }
        else
            tmp[pos++] = nums[left++];  // 若左右两个元素相等,left++,放入tmp数组中
    }
    // 左侧有剩余元素可以直接放入,在上方循环中记录过了
    while (left < left_end)
        tmp[pos++] = nums[left++];
    // 右侧有剩余元素同样可以直接放入,右侧升序,左侧元素结束,即右侧不再能构成逆序对
    while (right < right_end)
        tmp[pos++] = nums[right++];
    // 将tmp中数据拷回
    for (int i = begin; i < end; ++i)
        nums[i] = tmp[i];
}
int reversePairs(std::vector<int>& record)
{
    int ret = 0;
    std::vector<int> tmp(record.size());
    merge_count(record, 0, tmp.size(), ret, tmp);
    return ret;
}

//计算右侧小于当前元素的个数
//给你⼀个整数数组nums,按要求返回⼀个新数组counts.数组counts有该性质: counts[i]的值是nums[i]右侧小于nums[i]的元素的数量
//输入: nums = [5, 2, 6, 1]
//输出: [2, 1, 1, 0]
//  5 的右侧有 2 个更小的元素(2 和 1)
//  2 的右侧仅有 1 个更小的元素(1)
//  6 的右侧有 1 个更小的元素(1)
//  1 的右侧有 0 个更小的元素
void merge_count(std::vector<int>& nums, int begin, int end, std::vector<int>& ret, std::vector<int>& tmpnum, std::vector<int>& tmpcnt, std::vector<int>& index, std::vector<int>& tmpindex)
{
    if (end - begin <= 1)
        return;
    // 进行归并,将一整个数组分为两部分,左右各自统计好内部的逆序对数量,并排降序
    int mid = (begin + end) / 2;
    merge_count(nums, begin, mid, ret, tmpnum, tmpcnt, index, tmpindex);
    merge_count(nums, mid, end, ret, tmpnum, tmpcnt, index, tmpindex);

    // 划分出左右两个数组的范围
    int left_begin = begin, left_end = mid;
    int right_begin = mid, right_end = end;
    int left = left_begin, right = right_begin;
    int pos = begin;
    // 循环迭代指针,遍历左侧数组,在右侧数组中找寻比当前元素小的元素
    while (left < left_end && right < right_end)
    {
        if (nums[left] > nums[right])
        {
            // 若右侧当前元素小于左侧当前元素,构成逆序,且右侧为降序,右侧数组中该元素后所有元素均与其构成逆序
            // left++,并将其放入tmpnum数组中,并在tmpcnt存入当前元素的逆序个数,且续存当前元素在原始数组中的位置
            tmpnum[pos] = nums[left];
            tmpcnt[pos] = ret[left] + right_end - right;
            tmpindex[pos] = index[left];
            ++pos, ++left;
        }
        else
        {
            // 若右侧当前元素大于等于左侧当前元素,不够成逆序,右侧为降序
            // right++,并将其放入tmpnum数组中,并在tmpcnt存入当前元素的逆序个数,且续存当前元素在原始数组中的位置
            tmpnum[pos] = nums[right];
            tmpcnt[pos] = ret[right];
            tmpindex[pos] = index[right];
            ++pos, ++right;
        }
    }

    // 将左侧剩余数据直接拷回,右侧为降序,右侧数据结束时,左侧不能构成逆序
    while (left < left_end)
    {
        tmpnum[pos] = nums[left];
        tmpcnt[pos] = ret[left];
        tmpindex[pos] = index[left];
        ++pos, ++left;
    }
    // 将右侧剩余数据直接拷回,右侧剩余数据在上方循环已记录
    while (right < right_end)
    {
        tmpnum[pos] = nums[right];
        tmpcnt[pos] = ret[right];
        tmpindex[pos] = index[right];
        ++pos, ++right;
    }
    // 将数据拷回
    for (int i = begin; i < end; ++i)
    {
        nums[i] = tmpnum[i];
        ret[i] = tmpcnt[i];
        index[i] = tmpindex[i];
    }
}
std::vector<int> countSmaller(std::vector<int>& nums)
{
    std::vector<int> tmpnum(nums.size());
    std::vector<int> tmpcnt(nums.size());
    std::vector<int> ret(nums.size());
    std::vector<int> index(nums.size());
    std::vector<int> tmpindex(nums.size());
    for (size_t i = 0; i < index.size(); ++i)
        index[i] = i;
    merge_count(nums, 0, nums.size(), ret, tmpnum, tmpcnt, index, tmpindex);
    std::vector<std::pair<int, int>> res(nums.size());
    for (size_t i = 0; i < res.size(); ++i)
    {
        res[i].first = ret[i];
        res[i].second = index[i];
    }
    std::sort(res.begin(), res.end(), [](std::pair<int, int>& left, std::pair<int, int>& right) -> bool
        {
            return left.second < right.second;
        });
    for (size_t i = 0; i < nums.size(); ++i)
        ret[i] = res[i].first;
    return ret;
}

//翻转对
//给定⼀个数组nums,如果i < j且nums[i] > 2*nums[j] 我们就将(i, j)称作⼀个重要翻转对
//你需要返回给定数组中的重要翻转对的数量
//输入: [1, 3, 2, 3, 1]
//输出: 2
void merge_count_2(std::vector<int>& nums, int begin, int end, int& ret, std::vector<int>& tmp)
{
    // 同逆序对思路相同
    if (end - begin <= 1)
        return;
    int mid = (begin + end) / 2;
    merge_count_2(nums, begin, mid, ret, tmp);
    merge_count_2(nums, mid, end, ret, tmp);

    int left_begin = begin, left_end = mid;
    int right_begin = mid, right_end = end;
    int left = left_begin, right = right_begin;

    // 先统计有多少满足条件的
    while (left < left_end)
    {
        // 左右两侧数组均为升序,找到不满足条件的右侧数组的元素位置
        while (right < right_end && (long long)nums[left] > (long long)2 * nums[right])
            ++right;
        // 该元素前面的所有元素均满足
        ret += right - right_begin;
        ++left;
    }
    // 再进行升序归并
    int pos = begin;
    left = left_begin, right = right_begin;
    while (left < left_end && right < right_end)
    {
        if (nums[left] < nums[right])
            tmp[pos++] = nums[left++];
        else
            tmp[pos++] = nums[right++];
    }
    while (left < left_end)
        tmp[pos++] = nums[left++];
    while (right < right_end)
        tmp[pos++] = nums[right++];
    for (int i = begin; i < end; ++i)
        nums[i] = tmp[i];
}
int reverseImportantPairs(std::vector<int>& nums)
{
    int ret = 0;
    std::vector<int> tmp(nums.size());
    merge_count_2(nums, 0, nums.size(), ret, tmp);
    return ret;
}

// 动态规划

//斐波那契数列模型

//第 N 个泰波那契数
//泰波那契序列Tn定义如下:
//T0 = 0, T1 = 1, T2 = 1,且在 n >= 0 的条件下 Tn + 3 = Tn + Tn + 1 + Tn + 2
//给你整数 n,请返回第 n 个泰波那契数 Tn 的值
//输入: n = 4
//输出: 4
int tribonacci(int n)
{
    size_t t[3] = { 0, 1, 1 };
    for (size_t i = 3; i <= n; i += 3)
    {
        t[0] += t[1] + t[2];
        t[1] += t[0] + t[2];
        t[2] += t[0] + t[1];
    }
    return t[n % 3];
}

//三步问题
//有个小孩正在上楼梯,楼梯有n阶台阶,小孩⼀次可以上1阶,2阶或3阶
//实现⼀种⽅法,计算小孩有多少种上楼梯的方式,结果可能很大,你需要对结果模1000000007
//输入: n = 3
//输出: 4
int waysToStep(int n)
{
    size_t step[3] = { 1, 1, 2 };
    for (size_t i = 3; i <= n; i += 3)
    {
        step[0] = (step[0] + step[1] + step[2]) % 1000000007;
        step[1] = (step[0] + step[1] + step[2]) % 1000000007;
        step[2] = (step[0] + step[1] + step[2]) % 1000000007;
    }
    return step[n % 3];
}

//使用最小花费爬楼梯
//给你⼀个整数数组cost,其中cost[i]是从楼梯第i个台阶向上爬需要⽀付的费用
//⼀旦你⽀付此费用,即可选择向上爬⼀个或者两个台阶
//你可以选择从下标为0或下标为1的台阶开始爬楼梯,请你计算并返回达到楼梯顶部的最低花费
//输入: cost = [10, 15, 20]
//输出: 15
int minCostClimbingStairs(std::vector<int>& cost)
{
    std::vector<int> fee(cost.size() + 1, 0);
    for (size_t i = 2; i < fee.size(); ++i)
    {
        // dp[i] = min(dp[i - 2] + 该台阶向上花费, dp[i - 1] + 该台阶向上花费)
        fee[i] = (fee[i - 2] + cost[i - 2]) > (fee[i - 1] + cost[i - 1]) ? \
            (fee[i - 1] + cost[i - 1]) : (fee[i - 2] + cost[i - 2]);
    }
    return fee[cost.size()];
}

//解码方法
//⼀条包含字母 A - Z 的消息通过以下映射进行了编码: 'A' -> "1", 'B' -> "2", ... ,'Z' -> "26"
//要解码已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)
//"11106"可以映射为: "AAJF",将消息分组为(1 1 10 6), "KJF",将消息分组为(11 10 6)
//给你⼀个只含数字的非空字符串s,请计算并返回解码方法的总数
//题⽬数据保证答案肯定是⼀个32位的整数
//输入: s = "12"
//输出: 2 
//  它可以解码为"AB"(1 2)或者"L"(12)
int numDecodings(std::string s)
{
    std::vector<int> dp(s.size(), 0);
    // 处理头两个字符的情况
    if (s[0] != '0')
        dp[0] = 1;
    // 处理边界情况
    if (s.size() == 1)
        return dp[0];
    if (s[1] != '0')
        dp[1] += dp[0];
    int num = (s[0] - '0') * 10 + s[1] - '0';
    if (num >= 10 && num <= 26)
        dp[1] += 1;

    // dp[i] = (该位数字是否可以单独编码 ? dp[i - 1] : 0) + (该位数字是否可以和上一个数字进行合并编码 ? dp[i - 2] : 0);
    for (size_t i = 2; i < dp.size(); ++i)
    {
        // 判断该位数字是否可以单独编码
        if (s[i] != '0')
            dp[i] += dp[i - 1];
        // 判断该位数字是否可以和上一个数字进行合并编码
        int num = (s[i - 1] - '0') * 10 + s[i] - '0';
        if (num >= 10 && num <= 26)
            dp[i] += dp[i - 2];
    }
    return dp.back();
}

//路径问题

//不同路径
//⼀个机器人位于⼀个m * n网格的左上角
//机器⼈每次只能向下或者向右移动⼀步,机器人试图达到网格的右下角问总共有多少条不同的路径
//输入: m = 3, n = 7
//输出: 28
int uniquePaths(int m, int n)
{
    std::vector<std::vector<int>> map(m + 1, std::vector<int>(n + 1, 0));
    map[1][1] = 1;
    // dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    for (size_t i = 1; i < map.size(); ++i)
    {
        for (size_t j = 1; j < map[i].size(); ++j)
            map[i][j] += map[i - 1][j] + map[i][j - 1];
    }

    return map[m][n];
}

//不同路径II
//⼀个机器人位于⼀个m * n网格的左上角
//机器人每次只能向下或者向右移动⼀步,机器人试图达到网格的右下角
//现在考虑网格中有障碍物,那么从左上角到右下角将会有多少条不同的路径
//网格中的障碍物和空位置分别用1和0来表示
//输入: obstacleGrid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
//输出: 2
//3x3网格的正中间有⼀个障碍物
//从左上角到右下角⼀共有2条不同的路径, 向右->向右->向下->向下, 向下->向下->向右->向右
int uniquePathsWithObstacles(std::vector<std::vector<int>>& obstacleGrid)
{
    std::vector<std::vector<int>> map(obstacleGrid.size() + 1, std::vector<int>(obstacleGrid[0].size() + 1, 0));
    map[1][1] = 1;
    for (size_t i = 1; i < map.size(); ++i)
    {
        for (size_t j = 1; j < map[i].size(); ++j)
        {
            // dp[i][j] = 该位置是否有障碍物 ? 0 : dp[i - 1][j] + dp[i][j - 1]
            if (obstacleGrid[i - 1][j - 1] == 1)
                map[i][j] = 0;
            else
                map[i][j] += (map[i - 1][j] + map[i][j - 1]);
        }
    }
    return map.back().back();
}

//礼物的最大价值
//在⼀个m * n的棋盘的每⼀格都放有⼀个礼物,每个礼物都有⼀定的价值(价值大于0)
//你可以从棋盘的左上⻆开始拿格子里的礼物,并每次向右或者向下移动⼀格,直到到达棋盘的右下角
//给定⼀个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物
//输入: [1, 3, 1],
//      [1, 5, 1],
//      [4, 2, 1]
//输出: 12
//  路径 1 -> 35 -> 2 -> 1
int jewelleryValue(std::vector<std::vector<int>>& frame)
{
    for (size_t i = 0; i < frame.size(); ++i)
    {
        for (size_t j = 0; j < frame[i].size(); ++j)
        {
            size_t up = i == 0 ? 0 : frame[i - 1][j];
            size_t left = j == 0 ? 0 : frame[i][j - 1];
            // dp[i][j] = max(上方礼物数量, 左侧礼物数量) + 当前位置礼物数量
            frame[i][j] += std::max<size_t>(up, left);
        }
    }
    return frame.back().back();
}

//下降路径最小和
//给你⼀个n * n的方形整数数组matrix,请你找出并返回通过matrix的下降路径的最小和
//下降路径可以从第⼀行中的任何元素开始,并从每⼀行中选择⼀个元素,在下⼀行选择的元素和当前行所选元素最多相隔⼀列
//位置(row, col)的下⼀个元素应当是(row + 1, col - 1),(row + 1, col),(row + 1, col + 1)
//输入: matrix = [[2, 1, 3], [6, 5, 4], [7, 8, 9]]
//输出: 13
int minFallingPathSum(std::vector<std::vector<int>>& matrix)
{
    for (int i = 1; i < matrix.size(); ++i)
    {
        for (int j = 0; j < matrix[i].size(); ++j)
        {
            int min = matrix[i - 1][j];
            for (int k = -1; k <= 1; ++k)
            {
                if (k + j < 0 || k + j >= matrix[i].size())
                    continue;
                int tmp = matrix[i - 1][j + k];
                if (tmp < min)
                    min = tmp;
            }
            // dp[i][j] = min(dp[i + 1, j - 1], dp[i - 1][col], dp[i - 1][j + 1]) + 当前位置数值
            matrix[i][j] += min;
        }
    }
    // 最后找出最后一行的最小值
    std::vector<int>& low = matrix.back();
    int min = low[0];
    for (size_t i = 1; i < low.size(); ++i)
    {
        if (min > low[i])
            min = low[i];
    }
    return min;
}

//最小路径和
//给定⼀个包含非负整数的m * n网格grid,请找出⼀条从左上角到右下角的路径,使得路径上的数字总和为最小
//说明: 每次只能向下或者向右移动⼀步
//输入: grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
//输出: 7
//  因为路径1 -> 3 -> 1 -> 1 -> 1的总和最小
int minPathSum(std::vector<std::vector<int>>& grid)
{
    for (size_t i = 0; i < grid.size(); ++i)
    {
        for (size_t j = 0; j < grid[i].size(); ++j)
        {
            if (i == 0 && j == 0)
                continue;
            else if (i == 0)
                grid[i][j] += grid[i][j - 1];
            else if (j == 0)
                grid[i][j] += grid[i - 1][j];
            else
                grid[i][j] += std::min<int>(grid[i - 1][j], grid[i][j - 1]);
            // dp[i][j] = 当前位置数值 + min(上方位置的数值, 左方位置的数值)
        }
    }
    return grid.back().back();
}

//地下城游戏
//公主在地图右下角,地图是由M * N个房间组成的⼆维网格
//骑士最初在左上角的房间里,穿过地图并通过对抗恶魔来拯救公主
//骑士的初始健康点数为⼀个正整数,健康点数不能降至0或以下
//骑士在进入房间时会结算健康点数(若房间里的值为负整数将损失健康点数,值为正整数将增加健康点数
//骑士决定每次只向右或向下移动⼀步
//计算确保骑士能够拯救到公主所需的最低初始健康点数
//输入: [[-2  -3  3], [-5  -10  1], [10  30  -5]]
//输出: 7
//  最佳路径右 -> 右 -> 下 -> 下,则初始健康点数至少为7
int calculateMinimumHP(std::vector<std::vector<int>>& dungeon)
{
    std::vector<std::vector<int>> dp(dungeon.size() + 1, std::vector<int>(dungeon[0].size() + 1, INT_MAX));
    dp[dungeon.size()][dungeon.back().size() - 1] = dp[dungeon.size() - 1][dungeon.back().size()] = 1;
    // dp[i][j] 表示从该位置到右下角的最小健康点数
    for (int i = dungeon.size() - 1; i >= 0; --i)
    {
        for (int j = dungeon[i].size() - 1; j >= 0; --j)
        {
            // dp[i][j] = min(下方数值, 左方数值) - 当前数值
            dp[i][j] = std::min<int>(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
            // 若当前数值为正数,且使dp[i][j]为负数则需要将最小健康点数置1
            dp[i][j] = std::max<int>(1, dp[i][j]);
        }
    }
    return dp[0][0];
}

//简单多状态dp问题

//按摩师 (打家劫舍问题的变形, 小偷变成了按摩师)
//⼀个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接,在每次预约服务之间要有休息时间,因此她不能接受相邻的预约
//给定⼀个预约请求序列,替按摩师找到最优的预约集合,(总预约时间最长),返回总的分钟数
//输入: [1, 2, 3, 1]
//输出: 4
//  选择1号预约和3号预约,总时长 = 1 + 3 = 4
int massage(std::vector<int>& nums)
{
    // 从数组最后开始dp
    std::vector<int> dp(nums.size() + 3, 0);
    // dp[i] 表示当前位置最优预约选择,由于不接收相邻预约,dp时向后查找的元素为[i + 2, i + 3],i + 4绝对不可能,因为其可以选择i + 2 和 i + 4
    for (int i = nums.size() - 1; i >= 0; --i)
        dp[i] = nums[i] + std::max<int>(dp[i + 2], dp[i + 3]);
        // dp[i] = max(下下一个最优预约, 下下下个最优预约) + 选择当前数值
    return std::max<int>(dp[0], dp[1]);
}

//打家劫舍II
//你是⼀个专业的小偷,计划偷窃沿街的房屋,这个地方所有的房屋都围成⼀圈,这意味着第⼀个房屋和最后⼀个房屋是紧挨着的
//同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同⼀晚上被小偷闯入,系统会⾃动报警
//给定⼀个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,今晚能够偷窃到的最高金额
//输入: nums = [2, 3, 2]
//输出: 3
int rob(std::vector<int>& nums)
{
    // 处理边界
    if (nums.size() == 1)
        return nums[0];
    // 由于成环,选择第一家就不能选择第二家,故将其分为两种情况
    
    // 将第一家排除的选择方案
    std::vector<int> no_first_dp(nums.size() + 3, 0);
    for (int i = nums.size() - 1; i > 0; --i)
        no_first_dp[i] = nums[i] + std::max<int>(no_first_dp[i + 2], no_first_dp[i + 3]);
    
    // 将最后一家排除的选择方案
    std::vector<int> no_last_dp(nums.size() + 3, 0);
    for (int i = nums.size() - 2; i >= 0; --i)
        no_last_dp[i] = nums[i] + std::max<int>(no_last_dp[i + 2], no_last_dp[i + 3]);
    // 返回其中最大值
    return std::max<int>(std::max<int>(no_first_dp[1], no_first_dp[2]), std::max<int>(no_last_dp[0], no_last_dp[1]));
}

//删除并获得点数
//给你⼀个整数数组nums,你可以对它进行⼀些操作
//每次操作中,选择任意⼀个nums[i],删除它并获得nums[i]的点数,之后你必须删除所有等于nums[i] - 1和nums[i] + 1的元素
//开始你拥有0个点数,返回你能通过这些操作获得的最大点数
//输入: nums = [3, 4, 2]
//输出: 6
//  删除4获得4个点数,3也被删除,之后删除2获得2个点数,总共获得6个点数
int deleteAndEarn(std::vector<int>& nums)
{
    //选择x数字的时候,x - 1与x + 1是不能被选择的,与打家劫舍问题中,选择i位置的⾦额之后,就不能选择i - 1位置以及i + 1位置的金额
    //创建⼀个hash数组,将nums数组中每⼀个元素x,累加到hash数组下标为x的位置处,然后在hash数组上来⼀次打家劫舍
    int map[10001] = { 0 };
    for (size_t i = 0; i < nums.size(); ++i)
        map[nums[i]] += nums[i];
    int dp[10005] = { 0 };
    for (int i = 10000; i >= 0; --i)
        dp[i] = map[i] + std::max<int>(dp[i + 2], dp[i + 3]);
    return std::max<int>(dp[0], dp[1]);
}

//贪心算法

//柠檬水找零
//在柠檬水摊上,每⼀杯柠檬水的售价为5元,顾客⼀次购买⼀杯,然后向你付5元,10元,20元
//你必须给每个顾客正确找零,注意,⼀开始没有任何零钱
//给你⼀个整数数组bills,bills[i]是第i位顾客付的账,如果你能给每位顾客正确找零,返回true,否则返回false
//输入: bills = [5, 5, 5, 10, 20]
//输出: true
//  前3位顾客那里,按顺序收取3张5美元的钞票
//  第4位顾客那里,收取⼀张10元,并返还5元
//  第5位顾客那里,找还⼀张10元和⼀张5元
//  由于所有客户都得到了正确的找零,输出true
bool lemonadeChange(std::vector<int>& bills)
{
    // 分别记录5,10,20各有几张
    int money[3] = { 0 };
    for (size_t i = 0; i < bills.size(); ++i)
    {
        // 收到对应金额就进行++
        if (bills[i] == 5)
            ++money[0];
        else if (bills[i] == 10)
        {
            ++money[1];
            // 进行找零
            if (money[0] == 0)
                return false;
            else
                --money[0];
        }
        else
        {
            ++money[2];
            // 记录以找出的零钱
            int fee = 0;
            // 进行找零
            if (money[1] != 0)
            {
                fee += 10;
                --money[1];
            }
            while (money[0] != 0 && fee != 15)
            {
                --money[0];
                fee += 5;
            }
            if (fee != 15)
                return false;
        }
    }
    return true;
}

//将数组和减半的最少操作次数
//给你⼀个正整数数组nums,每⼀次操作中,你可以从nums中选择任意⼀个数并将它减小到恰好⼀半,在后续操作中你可以对减半过的数继续执行操作
//请你返回将nums数组和至少减少⼀半的最少操作数
//输入: nums = [5, 19, 8, 1]
//输出: 3
//  初始nums的和为5 + 19 + 8 + 1 = 33
//  以下是将数组和减少至少⼀半的⼀种方法:
//  选择19并减小为9.5,选择9.5并减小为4.75,选择8并减小为4
//  最终数组为[5, 4.75, 4, 1],和为5 + 4.75 + 4 + 1 = 14.75
//  nums的和减小了 33 - 14.75 = 18.25,减小的部分超过了初始数组和的⼀半,18.25 >= 33 / 2 = 16.5
int halveArray(std::vector<int>& nums)
{
    // 易知,最快减少一半的做法就是每次操作最大的数
    std::priority_queue<double> pq;
    double sum = 0;
    for (size_t i = 0; i < nums.size(); ++i)
    {
        sum += nums[i];
        pq.push(nums[i]);
    }
    // cnt记录操作次数
    int cnt = 0;
    // tmp记录当前和
    for (double tmp = sum; tmp * 2 > sum; ++cnt)
    {
        double t = pq.top();
        pq.pop();
        tmp -= t /= 2;
        pq.push(t);
    }
    return cnt;
}

//最大数
//给定⼀组非负整数nums,重新排列每个数的顺序(每个数不可拆分)使之组成⼀个最大的整数
//输出结果可能非常大,所以你需要返回⼀个字符串而不是整数
//输入: nums = [10, 2]
//输出: "210"
std::string largestNumber(std::vector<int>& nums)
{
    std::vector<std::string> map(nums.size());
    for (size_t i = 0; i < nums.size(); ++i)
        map[i] = std::to_string(nums[i]);
    //将所有的数字当成字符串处理
    //排序规则：
    // [A 拼接 B]大于[B 拼接 A],那么就AB
    // [A 拼接 B]等于[B 拼接 A],AB的顺序无所谓
    // [A 拼接 B]小于[B 拼接 A],那么就BA
    std::sort(map.begin(), map.end(), [](const std::string& left, const std::string& right)
        {
            return (left + right) > (right + left);
        });
    std::string ret;
    for (size_t i = 0; i < map.size(); ++i)
        ret += map[i];
    if (ret[0] == '0')
        return "0";
    return ret;
}

//摆动序列
//如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列
//第⼀个差(如果存在的话)可能是正数或负数,仅有⼀个元素或者含两个不等元素的序列也视作摆动序列
//  [1, 7, 4, 9, 2, 5]是⼀个摆动序列,因为差值(6, -3, 5, -7, 3)是正负交替出现的
//  相反[1, 4, 7, 2, 5]和[1, 7, 4, 5, 5]不是摆动序列,第⼀个序列是因为它的
//前两个差值都是正数,第⼆个序列是因为它的最后⼀个差值为零
//子序列可以通过从原始序列中删除⼀些(也可以不删除)元素来获得,剩下的元素保持其原始顺序
//给你⼀个整数数组nums,返回nums中作为摆动序列的最长子序列的长度
//输入: nums = [1, 17, 5, 10, 13, 15, 10, 5, 16, 8]
//输出: 7
//  这个序列包含几个长度为7摆动序列,其中⼀个是[1, 17, 10, 13, 10, 16, 8],各元素之间的差值为(16, -7, 3, -3, 6, -8)
int wiggleMaxLength(std::vector<int>& nums)
{
    if (nums.size() == 1)
        return 1;
    int ret = 0;
    int left = 0;
    for (size_t i = 0; i < nums.size() - 1; ++i)
    {
        int right = nums[i + 1] - nums[i];
        if (right == 0)
            continue;
        else if (left * right <= 0)
            ++ret;
        left = right;
    }
    return ret + 1;
}

int main()
{
    ;
    return 0;
}